package com.hy.node;

public class RemoveNthFromEnd {

    /**
     * 19.删除链表的倒数第N个节点
     * 力扣题目链接
     *
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     *
     * 进阶：你能尝试使用一趟扫描实现吗？
     * 输入： head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 
     * 示例 2：输入：head = [1], n = 1 输出：[] 
     * 示例 3： 输入：head = [1,2], n = 1 输出：[1]
     */

    static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    static ListNode removeNthFromEnd(ListNode head,int n){
        ListNode dummy = new ListNode(-1, head);

        ListNode fast = dummy;
        ListNode slow = dummy;

        while (n-- > 0){
           fast =  fast.next;
        }
        // 记住 待删除节点slow 的上一节点
        ListNode pre = null;
        while (fast != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        // 上一节点的next指针绕过 待删除节点slow 直接指向slow的下一节点
        pre.next = slow.next;
        slow.next = null;

        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5,null);
        ListNode listNode4 = new ListNode(4,listNode5);
        ListNode listNode3 = new ListNode(3,listNode4);
        ListNode listNode2 = new ListNode(2,listNode3);
        ListNode listNode1 = new ListNode(1,listNode2);
        // 删除 倒数第4个元素。
        System.out.println(removeNthFromEnd(listNode1,2));

    }
}
